from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def bisect_low(target, array):
            l = 0
            r = len(array) - 1
            while l <= r:
                mid = (l + r) >> 1
                if array[mid] <= target:
                    l = mid + 1
                else:
                    r = mid - 1
            return l - 1
        i = bisect_low(target, matrix[0])
        if i == -1: return False
        for j in range(0, len(matrix)):
            if matrix[j][i] == target:
                return True
        return False

if __name__ == '__main__':
    s = Solution()
    r = s.searchMatrix([[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]], 19)